给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

#使用前缀和的情况和使用滑动窗口的情况有些相似 但是滑动窗口的要求窗口左移 右移有单独的增长趋势
#比如这里的数组包含负数 那么就无法确定子数组和的右移就是增加 左移就是减少 就无法使用滑动窗口
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        #看了题解是借组前缀和来解决的  pre[i]就是开始到i这个元素的和  pre[i]-pre[j]就是子数组[j---i]的和
        #针对这题的思路具体看题解
        pre_map = collections.defaultdict(int)
        #pre_map[0] += 1 
        cur_sum = 0
        res = 0
        for i, n in enumerate(nums):
            cur_sum += n
            
            if cur_sum == k:
                res += 1
            if (cur_sum-k) in pre_map: #这边两个可以同时出现 比如[0,0,0,0]目标为0 任何一个前缀和都满足k 同时任何一个子数组也满足k
                res += pre_map[cur_sum-k]
            
            pre_map[cur_sum] += 1 #这个要放在后面 因为寻找的前缀和不应该包括当前这个
            
        return res
        
        
        #连续子数组-----滑动窗口 #不行 因为元素可以是负数 无法确定子数组和的右移就是增加 左移就是减少
#         if len(nums)==0:
#             return 0
        
#         left, right = 0, 0
#         cur_sum = nums[0]
#         res = 0
#         while left<=right and right<len(nums):
#             if cur_sum == k:
#                 res += 1 #也算是上一次操作卡出来的子数组 且符合while条件 是合法的才进行判断
            
#             if cur_sum >= k:
#                 if left < right:
#                     cur_sum -= nums[left]
#                     left += 1
#                 elif left == right:
#                     if left < len(nums)-1:
#                         cur_sum = nums[right+1]
#                     left += 1
#                     right += 1
                    
#             elif cur_sum < k:
#                 right += 1
#                 if right < len(nums):
#                     cur_sum += nums[right]
        
#         return res